package leetcode.sort;

import leetcode.erfen.FindMedianSortedArrays4;

/**
 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。


 示例 1:

 输入: [3,2,1,5,6,4] 和 k = 2
 输出: 5
 */
public class FindKthLargest215 {

    public static void main(String[] args) {
        int [] arr1 = new int[]{3,3,4,3,3,3,3};

        int res = new FindKthLargest215().findKthLargest(arr1, 1);
        System.out.println(res);

    }
    public int findKthLargest(int[] nums, int k) {
        int l=0,r=nums.length-1,target = nums.length-k;

        while (l<r){
            int mid = partition(nums, l, r);
            if(mid==target)
                return nums[mid];
            else if(mid<target){
                l = mid+1;
            }else
                r = mid-1;
        }
        return  -1;
    }


    private int partition(int [] nums,int l,int r){
        int v = nums[l];

        int j=l;

        //[l...r]范围内
        for (int i = l+1; i <= r; i++) {
            if(nums[i] < v)
                swap(nums,i,++j);
        }
        swap(nums,j,l);//把标定点放在这个位置

        return  j;//标定点所处的位置
    }

    private void swap(int []nums,int i,int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}